//
// Description: 5728. 最少侧跳次数
// Created by Loading on 2021/4/11.
//

#include <bits/stdc++.h>

using namespace std;

/* 贪心算法 */
int minSideJumps(vector<int> &obstacles) {
    int n = obstacles.size();
    if (n < 3) {
        return 0;
    }
    if (n == 3) {
        return obstacles[1] == 2 ? 1 : 0;
    }

    int current = 2;//当前赛道
    int minJumps = 0;//最少侧跳次数
    for (int i = 0; i < n;) {
        if (obstacles[i] == current) {//当前赛道有障碍，需要侧跳
            minJumps++;
            if (obstacles[i - 1] != 0) {//只有一种侧跳选择，直接更新赛道
                current = 6 - obstacles[i - 1] - current;
                ++i;
            } else {//两种侧跳选择，贪心选取可以走的更远的赛道
                int index = i + 1;
                while (index < n - 1) {//定位侧跳后再次遇到障碍的索引index
                    if (obstacles[index] == current || obstacles[index] == 0) {
                        index++;
                    } else {
                        break;
                    }
                }
                if (index == n - 1) {//无论怎样侧跳都将再也不会遇到障碍，侧跳结束，直接返回
                    return minJumps;
                } else {//向某一侧侧跳后仍会遇到障碍，选取另一侧走的更远的赛道侧跳
                    current = 6 - obstacles[index] - current;
                }
                i = index;
            }
        } else {//当前赛道无障碍，继续前行
            ++i;
        }
    }

    return minJumps;
}

/* 动态规划 */
int minSideJumps_dp(vector<int> &obstacles) {
    //dp[i][j]，表示在i位置，j赛道时的最小侧跳次数
    /* 初始化dp数组时，可以使用一个相对较大的值，如果使用INT_MAX，则不要忘记 - 1，否则计算过程中会出现 + 1，导致越界 */
    vector<vector<int>> dp(obstacles.size(), vector<int>(3, INT_MAX - 1));
    //初始位置为第2赛道，所以2赛道不需侧跳，其他赛道都需侧跳一次
    dp[0][0] = dp[0][2] = 1;
    dp[0][1] = 0;

    for (int i = 1; i < dp.size(); ++i) {
        //未从其他赛道侧跳过来时
        for (int j = 0; j < 3; ++j) {
            //当前位置无障碍时，直接通过，有障碍时，必须侧跳
            if (obstacles[i] != j + 1) {
                dp[i][j] = dp[i - 1][j];
            }
        }

        for (int j = 0; j < 3; ++j) {
            //当前位置无障碍，可以从其他赛道侧跳至当前赛道
            if (obstacles[i] != j + 1) {
                //计算其他两个赛道是哪两个
                int side1 = (j + 1) % 3;
                int side2 = (j + 2) % 3;
                //从其他赛道侧跳过来时，最少的侧跳次数
                int min_afterSideJumps = min(dp[i][side1], dp[i][side2]) + 1;
                //选取两种情况（是否从其他赛道跳过来）下的最优解
                dp[i][j] = min(min_afterSideJumps, dp[i][j]);
            }
        }
    }

    return *min_element(dp.back().begin(), dp.back().end());
}

int main() {
    vector<int> obstacles = {0, 2, 1, 0, 3, 0};
    cout << minSideJumps(obstacles) << endl;
    cout << minSideJumps_dp(obstacles) << endl;
}